Solution: Regions Cut by Slashes

Statement#

An $n \times n$ grid is composed of $n$, $1 \times 1$ squares, where each $1 \times 1$ square consists of a “/”, “\”, or a blank space. These characters divide the square into adjacent regions.

Given the grid represented as a string array, return the number of regions.

Note:

1. Backslash characters are escaped, so “\” is represented as “\\”.
2. A $1 \times 1$ square in the grid will be referred to as a box.

Constraints:

• The grid consists of only “/”, “\”, or " " characters.
• 1 $\leq$ grid.length $\leq$ 30

The following demonstration shows how the grid can be visualized:

Solution#

The idea is to divide each $1 \times 1$ box in the grid into four regions representing its north, west, east, and south regions. At the start, an $n \times n$ grid will contain $(4 \times n \times n)$ regions. We will gradually reduce the number of regions by merging the regions inside each box based on the character they contain and then connecting them with their neighboring boxes. This merging and connecting will be done using the union find algorithm. In the union find algorithm, the union by rank and path compression optimizations will be applied. In the end, the number of connected components will represent the correct number of regions inside the grid.

Here’s how the algorithm works:

• We create a parent array containing $4 \times n \times n$ elements where each element equals its corresponding index.

  • Every four consecutive elements in this array represent a $1\times1$ box in the grid.

  • We associate each $1\times1$ grid square with four nodes—north, west, east, and south—representing four triangles inside the square. That’s how every one of these four elements inside the parent list represents the north, west, east, and south components of the box, respectively.

  • Each element in the array is initially equal to its respective index. For example:

    • The grid[0][0] box will comprise of the elements: 0, 1, 2, and 3.

    • The grid[0][1] box will comprise of the elements: 4, 5, 6, and 7, and so on.

• Next, we traverse each character of the grid array:

• We use the union method to merge the regions within each box depending on the character it contains:

  • If the box contains a “/” character, it will be partitioned into two regions. Therefore, we will merge the north-west and east-south regions to convert the box into two connected components.

  • If the box contains a “\\” character, it will be partitioned into two regions. Therefore, we will merge the north-east and west-south regions to convert the box into two connected components.

  • If the box contains a " " character, it will be converted to a single region. Therefore, we combine all four regions of the box to convert the box into a single connected component.

The illustration below shows how the regions within a box are merged:

• Next, we connect the current box with the neighboring boxes on it’s top, bottom, left, and right:

  • The north region of the current box connects with the south region of the box above it.

  • The south region of the current box connects with the north region of the box below it.

  • The west region of the current box connects with the east region of the box to its left.

  • The east region of the current box connects with the west region of the box to its right.

• After the grid array has been traversed completely, the number of connected components in parent array are equal to the correct number of regions in the grid. So, we will traverse the parent array to find the number of connected components:

  • We maintain a variable, count, initialized to 0 to count the number of connected components.

  • For each element, parents[i], we will use the find(parents[i]) method to check if the current node is a parent of itself, i.e. the current element parents[i] is equal to its respective index, i:

    • If it is, we have found a connected component and increment the count variable.

    • Otherwise, we move forward.

• After the parent array has been traversed completely, we return count as it contains the number of regions in the grid.

The slides below illustrate how the algorithm runs:

Let’s take a look at the code for this solution below:

Time complexity#

The time complexity of this solution is $O(n^2)$, (where $n$ is the length of the grid) and can be calculated as:

• The nested loops iterate over each character in the grid, resulting in $O(n^2)$ iterations.

• The time complexity of the the union and find functions is $O( \alpha n)$ as both path compression and union find by rank are being used. $\alpha n$ is almost constant time and grows very slowly with the input size, so the time complexity of both these functions can be considered as constant time for practical purposes.

• The loop to find the number of connected components traverses the parent array once, resulting in $O(4 \times n \times n)$ iterations.

Therefore, the overall time complexity becomes $O(n^2 \times \alpha n + (4\times n \times n))$, which simplifies to $O(n^2)$.

Space Complexity#

The space complexity of this solution is $O(n^2)$ and can be calculated as:

• Space occupied by the parent array: $O(4 \times n \times n)$.

• Space occupied by the rank array: $O(4 \times n \times n)$.

Therefore, the overall time complexity is $O(2(4\times n \times n))$, which simplifies to $O(n^2)$.